#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int subarraysDivByK(vector<int>& nums, int k) {
    map<int, int> hash;
    int count = 0;
    int presum = 0;
    hash[0] = 1;
    for (int i = 0; i < nums.size(); i++) {
        presum += nums[i];
        int tmp = (presum % k + k) % k;
        if (hash.count(tmp)) {
            count += hash[tmp];
        }
        hash[tmp]++;
    }
    return count;
}